package org.example.myleet.rosalind.nkew;

import org.example.myleet.rosalind.utils.NewickTreeNode;
import org.example.myleet.rosalind.utils.NewickTreeUtil;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
        String line;
        while (null != (line = br.readLine())) {
            line = line.trim();
            if (line.length() < 1) {
                continue;
            }
            NewickTreeNode root = NewickTreeUtil.parse(null, line);
            String[] targets = br.readLine().trim().split(" ");
            List<String> path0 = new ArrayList<>();
            findPath(root, targets[0], path0);
            List<String> path1 = new ArrayList<>();
            findPath(root, targets[1], path1);
            int distance = 0, i = 0, j = 0;
            String p0, p1;
            while (i < path0.size() && j < path1.size()) {
                p0 = path0.get(i);
                p1 = path1.get(j);
                if (!p0.equals(p1)) {
                    //路径上不同的节点才开始计入距离
                    distance += Integer.parseInt(p0.split(":")[1]);
                    distance += Integer.parseInt(p1.split(":")[1]);
                }
                ++i;
                ++j;
            }
            //剩下未遍历完的路径继续遍历并计入距离中
            while (i < path0.size()) {
                p0 = path0.get(i);
                String[] p0s = p0.split(":");
                distance += Integer.parseInt(p0s[1]);
                ++i;
            }
            while (j < path1.size()) {
                p1 = path1.get(j);
                String[] p1s = p1.split(":");
                distance += Integer.parseInt(p1s[1]);
                ++j;
            }
            System.out.printf("%d ", distance);
        }
        System.out.println();
        br.close();
    }

    private static boolean findPath(NewickTreeNode parent, String target, List<String> path) {
        if (null == parent.getChildren() || 1 > parent.getChildren().size()) {
            return false;
        }
        //考虑value可能是空的，会影响判断节点是否相同，此处使用节点的唯一id作为判断依据
        path.add(parent.getId() + ":" + parent.getWeight());
        for (NewickTreeNode child : parent.getChildren()) {
            if (child.getValue().equals(target)) {
                //找到目标节点，加入到路径中并返回
                path.add(child.getId() + ":" + child.getWeight());
                return true;
            } else {
                if (findPath(child, target, path)) {
                    return true;
                }
            }
        }
        //回溯
        path.remove(path.size() - 1);
        return false;
    }
}
